﻿#pragma once
#include <ostream>

#include "Index.h"

class IReverseListBetween
{
public:
	/**
	* 链表内指定区间反转.
	* https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
	*
	* 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度O(1)。
	* 例如：
	* 给出的链表为 1→2→3→4→5→NULL, m=2,n=4
	* 返回 1→4→3→2→5→NULL.

	* 数据范围： 链表长度 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足 ∣val∣≤1000
	* 要求：时间复杂度 O(n) ，空间复杂度 O(n)
	* 进阶：时间复杂度 O(n)，空间复杂度 O(1)
	*/
	virtual  ListNode* reverseListBetween(ListNode* head, int m, int n) = 0;
};

class ReverseListBetween
{
public:
	class Solution :public IReverseListBetween
	{
	public:
		ListNode* reverseListBetween(ListNode* head, int m, int n) override
		{
			if (head == nullptr || m > n || m <= 0 || n <= 0)
				return nullptr;

			//头插法
			ListNode dummyHead(0, head);

			//走到开始反转的结点
			ListNode* pre = &dummyHead;
			ListNode* cur = head;
			for (int i = 0; i < m - 1; ++i)
			{
				pre = cur;
				cur = cur->next;
			}

			//开始反转前记录
			ListNode* preBeforeReverse = pre;
			ListNode* curBeforeReverse = cur;

			//从m到n进行 n-m+1 次的反转
			const int reverseSize = n - m + 1;
			pre = nullptr;
			for (int i = 0; i < reverseSize; ++i)
			{
				ListNode* next = cur->next;
				cur->next = pre;
				pre = cur;
				cur = next;
			}

			//拼合反转后的区间
			preBeforeReverse->next = pre;//此时pre指向反转后的链表头
			curBeforeReverse->next = cur;//此时cur执行反转后的链表尾的next

			//返回结果
			return dummyHead.next;
		}
	};
};

